package com.sheng.leetcode.year2022.month09.day21;

import javafx.util.Pair;
import org.junit.Test;

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;

/**
 * @author liusheng
 * @date 2022/09/21
 *<p>
 * 854. 相似度为 K 的字符串<p>
 *<p>
 * 对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，<p>
 * 能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。<p>
 * 给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。<p>
 *<p>
 * 示例 1：<p>
 * 输入：s1 = "ab", s2 = "ba"<p>
 * 输出：1<p>
 *<p>
 * 示例 2：<p>
 * 输入：s1 = "abc", s2 = "bca"<p>
 * 输出：2<p>
 *<p>
 * 提示：<p>
 *<p>
 * 1 <= s1.length <= 20<p>
 * s2.length == s1.length<p>
 * s1和s2 只包含集合{'a', 'b', 'c', 'd', 'e', 'f'}中的小写字母<p>
 * s2 是 s1 的一个字母异位词<p>
 *
 * 来源：力扣（LeetCode）
 * 链接：<a href="https://leetcode.cn/problems/k-similar-strings">...</a>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0854 {

    @Test
    public void test01() {
//        String s1 = "ab", s2 = "ba";
        String s1 = "abc", s2 = "bca";
        System.out.println(new Solution().kSimilarity(s1, s2));
    }
}
class Solution {
    public int kSimilarity(String s1, String s2) {
        // 字符串长度
        int n = s1.length();
        // 队里中元素的key是字符串，value是找到的不同字符的后一位
        Queue<Pair<String, Integer>> queue = new ArrayDeque<Pair<String, Integer>>();
        // visit集合
        Set<String> visit = new HashSet<String>();
        queue.offer(new Pair<String, Integer>(s1, 0));
        // 将s1字符串放入集合中
        visit.add(s1);
        // step为移动次数
        int step = 0;
        while (!queue.isEmpty()) {
            // sz为当前队列中元素的数量
            int sz = queue.size();
            // 循环
            for (int i = 0; i < sz; i++) {
                // 返回并删除队列中的队首元素
                Pair<String, Integer> pair = queue.poll();
                // 获取队首元素的key
                String cur = pair.getKey();
                // 获取队首元素的value
                int pos = pair.getValue();
                // 如果队首元素等于字符串s2
                if (cur.equals(s2)) {
                    // 返回移动次数
                    return step;
                }
                // pos小余字符串长度n的情况下，找到从pos开始的两个字符串中第一个不相等的字符的位置
                while (pos < n && cur.charAt(pos) == s2.charAt(pos)) {
                    pos++;
                }
                // 从找到的不相等的字符的位置的后一位开始循环
                for (int j = pos + 1; j < n; j++) {
                    // 字符相等直接返回
                    if (s2.charAt(j) == cur.charAt(j)) {
                        continue;
                    }
                    // 对应位置的字符又不相等，并且j位置的字符和原来pos位置的字符相等时
                    if (s2.charAt(pos) == cur.charAt(j)) {
                        // 交换字符串cur中，j和pos位置的字符
                        String next = swap(cur, pos, j);
                        // 如果交换后的新字符串不在visit集合中
                        if (!visit.contains(next)) {
                            // 则将新字符串next放入集合
                            visit.add(next);
                            // 并添加到队列中
                            queue.offer(new Pair<String, Integer>(next, pos + 1));
                        }
                    }
                }
            }
            // 交换次数加1
            step++;
        }
        return step;
    }

    public String swap(String cur, int i, int j) {
        // 交换cur字符串中i和j位置的字符并返回新字符串
        char[] arr = cur.toCharArray();
        char c = arr[i];
        arr[i] = arr[j];
        arr[j] = c;
        return new String(arr);
    }
//    public int kSimilarity(String s1, String s2) {
//        int length = s1.length();
//        char[] c1 = s1.toCharArray();
//        char[] c2 = s2.toCharArray();
//        int ans = 0;
//        int start = 0;
//        while (start < length) {
//            if (c1[start] == c2[start]) {
//                start++;
//            } else {
//                int x = 0;
//                for (int i = start + 1; i < length; i++) {
//                    if (c1[start] == c2[i]) {
//                        if (c1[i] == c2[start]) {
//                            char c = c2[i];
//                            c2[i] = c2[start];
//                            c2[start] = c;
//                            break;
//                        } else {
//                            x = i;
//                        }
//                    }
//                }
//                if (c1[start] != c2[start]) {
//                    char c = c2[x];
//                    c2[x] = c2[start];
//                    c2[start] = c;
//                }
//                ans++;
//            }
//        }
//        return ans;
//    }
}
